Oalib search

标题关键字摘要作者全部

显示搜索

我的图书馆

OALib Journal期刊

ISSN: 2333-9721

费用：99美元

投稿

时间不限

( 2020 )

( 2019 )

( 2018 )

( 2017 )

自定义范围…

匹配条件： “Milenkovic Olgica” ，找到相关结果约220条。
列表显示的所有文章，均可免费获取

第1页/共220条

每页显示条

CaSPIAN: A Causal Compressive Sensing Algorithm for Discovering Directed Interactions in Gene Networks
Amin Emad, Olgica Milenkovic
PLOS ONE , 2014, DOI: 10.1371/journal.pone.0090781

Abstract: We introduce a novel algorithm for inference of causal gene interactions, termed CaSPIAN (Causal Subspace Pursuit for Inference and Analysis of Networks), which is based on coupling compressive sensing and Granger causality techniques. The core of the approach is to discover sparse linear dependencies between shifted time series of gene expressions using a sequential list-version of the subspace pursuit reconstruction algorithm and to estimate the direction of gene interactions via Granger-type elimination. The method is conceptually simple and computationally efficient, and it allows for dealing with noisy measurements. Its performance as a stand-alone platform without biological side-information was tested on simulated networks, on the synthetic IRMA network in Saccharomyces cerevisiae, and on data pertaining to the human HeLa cell network and the SOS network in E. coli. The results produced by CaSPIAN are compared to the results of several related algorithms, demonstrating significant improvements in inference accuracy of documented interactions. These findings highlight the importance of Granger causality techniques for reducing the number of false-positives, as well as the influence of noise and sampling period on the accuracy of the estimates. In addition, the performance of the method was tested in conjunction with biological side information of the form of sparse “scaffold networks”, to which new edges were added using available RNA-seq or microarray data. These biological priors aid in increasing the sensitivity and precision of the algorithm in the small sample regime.

保存相关文章

Sorting of Permutations by Cost-Constrained Transpositions
Farzad Farnoud,Olgica Milenkovic
Mathematics , 2010,

Abstract: We address the problem of finding the minimum decomposition of a permutation in terms of transpositions with non-uniform cost. For arbitrary non-negative cost functions, we describe polynomial-time, constant-approximation decomposition algorithms. For metric-path costs, we describe exact polynomial-time decomposition algorithms. Our algorithms represent a combination of Viterbi-type algorithms and graph-search techniques for minimizing the cost of individual transpositions, and dynamic programing algorithms for finding minimum cost cycle decompositions. The presented algorithms have applications in information theory, bioinformatics, and algebra.

保存相关文章

Information Theoretic Bounds for Tensor Rank Minimization over Finite Fields
Amin Emad,Olgica Milenkovic
Mathematics , 2011,

Abstract: We consider the problem of noiseless and noisy low-rank tensor completion from a set of random linear measurements. In our derivations, we assume that the entries of the tensor belong to a finite field of arbitrary size and that reconstruction is based on a rank minimization framework. The derived results show that the smallest number of measurements needed for exact reconstruction is upper bounded by the product of the rank, the order and the dimension of a cubic tensor. Furthermore, this condition is also sufficient for unique minimization. Similar bounds hold for the noisy rank minimization scenario, except for a scaling function that depends on the channel error probability.

保存相关文章

Semi-Quantitative Group Testing: A Unifying Framework for Group Testing with Applications in Genotyping
Amin Emad,Olgica Milenkovic
Mathematics , 2012, DOI: 10.1109/TIT.2014.2327630

Abstract: We propose a novel group testing method, termed semi-quantitative group testing, motivated by a class of problems arising in genome screening experiments. Semi-quantitative group testing (SQGT) is a (possibly) non-binary pooling scheme that may be viewed as a concatenation of an adder channel and an integer-valued quantizer. In its full generality, SQGT may be viewed as a unifying framework for group testing, in the sense that most group testing models are special instances of SQGT. For the new testing scheme, we define the notion of SQ-disjunct and SQ-separable codes, representing generalizations of classical disjunct and separable codes. We describe several combinatorial and probabilistic constructions for such codes. While for most of these constructions we assume that the number of defectives is much smaller than total number of test subjects, we also consider the case in which there is no restriction on the number of defectives and they may be as large as the total number of subjects. For the codes constructed in this paper, we describe a number of efficient decoding algorithms. In addition, we describe a belief propagation decoder for sparse SQGT codes for which no other efficient decoder is currently known. Finally, we define the notion of capacity of SQGT and evaluate it for some special choices of parameters using information theoretic methods.

保存相关文章

Weighted Superimposed Codes and Constrained Integer Compressed Sensing
Wei Dai,Olgica Milenkovic
Mathematics , 2008,

Abstract: We introduce a new family of codes, termed weighted superimposed codes (WSCs). This family generalizes the class of Euclidean superimposed codes (ESCs), used in multiuser identification systems. WSCs allow for discriminating all bounded, integer-valued linear combinations of real-valued codewords that satisfy prescribed norm and non-negativity constraints. By design, WSCs are inherently noise tolerant. Therefore, these codes can be seen as special instances of robust compressed sensing schemes. The main results of the paper are lower and upper bounds on the largest achievable code rates of several classes of WSCs. These bounds suggest that with the codeword and weighting vector constraints at hand, one can improve the code rates achievable by standard compressive sensing.

保存相关文章

On the Hardness of Approximating Stopping and Trapping Sets in LDPC Codes
Andrew McGregor,Olgica Milenkovic
Mathematics , 2007,

Abstract: We prove that approximating the size of stopping and trapping sets in Tanner graphs of linear block codes, and more restrictively, the class of low-density parity-check (LDPC) codes, is NP-hard. The ramifications of our findings are that methods used for estimating the height of the error-floor of moderate- and long-length LDPC codes based on stopping and trapping set enumeration cannot provide accurate worst-case performance predictions.

保存相关文章

Subspace Pursuit for Compressive Sensing Signal Reconstruction
Wei Dai,Olgica Milenkovic
Mathematics , 2008,

Abstract: We propose a new method for reconstruction of sparse signals with and without noisy perturbations, termed the subspace pursuit algorithm. The algorithm has two important characteristics: low computational complexity, comparable to that of orthogonal matching pursuit techniques when applied to very sparse signals, and reconstruction accuracy of the same order as that of LP optimization methods. The presented analysis shows that in the noiseless setting, the proposed algorithm can exactly reconstruct arbitrary sparse signals provided that the sensing matrix satisfies the restricted isometry property with a constant parameter. In the noisy setting and in the case that the signal is not exactly sparse, it can be shown that the mean squared error of the reconstruction is upper bounded by constant multiples of the measurement and signal perturbation energies.

保存相关文章

SET: an algorithm for consistent matrix completion
Wei Dai,Olgica Milenkovic
Mathematics , 2009,

Abstract: A new algorithm, termed subspace evolution and transfer (SET), is proposed for solving the consistent matrix completion problem. In this setting, one is given a subset of the entries of a low-rank matrix, and asked to find one low-rank matrix consistent with the given observations. We show that this problem can be solved by searching for a column space that matches the observations. The corresponding algorithm consists of two parts -- subspace evolution and subspace transfer. In the evolution part, we use a line search procedure to refine the column space. However, line search is not guaranteed to converge, as there may exist barriers along the search path that prevent the algorithm from reaching a global optimum. To address this problem, in the transfer part, we design mechanisms to detect barriers and transfer the estimated column space from one side of the barrier to the another. The SET algorithm exhibits excellent empirical performance for very low-rank matrices.

保存相关文章

DNA Codes that Avoid Secondary Structures
Olgica Milenkovic,Navin Kashyap
Mathematics , 2005,

Abstract: In this paper, we consider the problem of designing DNA sequences (codewords) for DNA storage systems and DNA computing that are unlikely to fold back onto themselves to form undesirable secondary structures. The paper addresses both the issue of enumerating the sequences with such properties and the problem of practical code construction.

保存相关文章

Semi-Quantitative Group Testing
Amin Emad,Olgica Milenkovic
Mathematics , 2012,

Abstract: We consider a novel group testing procedure, termed semi-quantitative group testing, motivated by a class of problems arising in genome sequence processing. Semi-quantitative group testing (SQGT) is a non-binary pooling scheme that may be viewed as a combination of an adder model followed by a quantizer. For the new testing scheme we define the capacity and evaluate the capacity for some special choices of parameters using information theoretic methods. We also define a new class of disjunct codes suitable for SQGT, termed SQ-disjunct codes. We also provide both explicit and probabilistic code construction methods for SQGT with simple decoding algorithms.

保存相关文章

第1页/共220条

每页显示条